RFC 6979
の適度なGoogle翻訳+手直し
デジタル署名アルゴリズム (DSA) および楕円曲線デジタル署名アルゴリズム (ECDSA) の決定論的使用法
概要
この文書は、決定論的なデジタル署名生成手順を定義する。この署名は、標準的なデジタル署名アルゴリズム (DSA) および楕円曲線デジタル署名アルゴリズム (ECDSA) のデジタル署名と互換性があり、変更されていない検証者によって処理することができる。検証者は、ここで説明されている手順を認識する必要はない。決定論的署名は、デジタル署名に関連する暗号セキュリティ機能を維持しながら、高品質の乱数源にアクセスする必要がないため、様々な環境に容易に実装できる。
このメモのステータス
この文書は、インターネット標準化過程の仕様ではなく、情報提供を目的として公開されている。
これは、他の RFC ストリームとは独立して、RFC シリーズへの貢献である。 RFCエディタは、この文書を独自の裁量で公開することを決定しており、実装または展開におけるその価値については一切表明していません。RFCエディタによって公開が承認された文書は、いかなるレベルのインターネット標準の候補でもありません。RFC 5741のセクション2を参照してください。
著作権表示
Copyright (c) 2013 IETF Trustおよび文書の著者として特定されている人物。All rights reserved.
1. はじめに
DSAとECDSAの特徴の一つは、署名生成ごとに新たな乱数（以下、kと表記）を生成する必要があることです。効果的なセキュリティを実現するには、kは暗号論的に安全なプロセスを用いて、モジュラー整数の集合からランダムかつ均一に選択されなければなりません。このプロセスにおけるわずかな偏りでさえ、署名方式への攻撃に利用される可能性があります。
暗号論的に安全な乱数源の必要性は、安全な乱数生成が困難な一部のアーキテクチャ、特にスマートカードなどの組み込みシステムにおいて、DSAおよびECDSA署名方式の導入を阻害する要因となっています。これらのシステムでは、公開鍵暗号標準（PKCS）#1 RFC 3447（「タイプ1」パディングを使用し、確率的署名方式（PSS）は使用しない）およびISO 9796-2 ISO-9796-2で規定されているRSA署名アルゴリズムが、計算コストが高いにもかかわらず、しばしば好まれます。これは、RSA（このようなパディング方式を使用）は決定論的であるため、乱数源を必要としないためです。 DSAとECDSAのランダム性は、実装のテストを困難にします。自動テストでは、実装が十分に高品質の乱数源を使用しているかどうかを確実に検出できません。
そのため、実装プロセスは壊滅的な障害に対してより脆弱になり、多くの場合、システムが展開され、攻撃に成功した後に発見されます。
「ランダム」な値kを生成するための決定論的なプロセスを使用することで、DSAとECDSAを決定論的なスキームに変えることができます。そのプロセスは、署名方式に期待される検証可能性と偽造不可能性の特性を維持するために、いくつかの暗号化特性を満たす必要があります。つまり、署名の秘密鍵を知らない人にとって、入力メッセージから対応する k 値へのマッピングは、ランダムかつ均一に選択された関数 (メッセージのセットから可能な k 値のセットへ) が返すものと計算的に区別できないものでなければなりません。
この文書では、そのような手順について説明します。この手順には以下の特徴があります。
生成された署名は、通常のDSAおよびECDSAと完全に互換性があります。署名を検証するエンティティは、変更する必要はなく、kの生成に使用されたプロセスを意識する必要もありません。
鍵ペアの生成は変更されません。既存の秘密鍵を決定論的DSAおよびECDSAで使用できます。
決定論的DSAおよびECDSAの使用は、秘密値または公開値の追加ストレージを必要としません。
決定論的DSAおよびECDSAは、通常のDSAおよびECDSAと同じ入力、つまり署名対象メッセージに対して暗号学的に安全なハッシュ関数を用いて計算されたハッシュ値に適用できます。
この文書で規定されている決定論的(EC)DSAの定義には、比較的恣意的な選択がいくつか行われています。これは、可能な限り普遍的に適用可能とし、含まれるテストベクトルの有用性を最大限に高めるためです。いくつかの可能なバリエーションについては、セクション3.6を参照してください。
鍵ペア生成には依然として乱数源が必要であることに留意してください。乱数の品質が問題となる組み込みシステムでは、鍵ペア生成をより制御された条件（例えば、特別なスマートカード初期化手順中や、宣誓した代理人の物理的な管理下）で実行するように設定できる場合が多く、あるいは鍵を別の場所で生成してデバイスにインポートすることも可能です。決定論的DSAとECDSAは、署名生成時の乱数の必要性のみを扱います。
1.1. 要件言語
本文書におけるキーワード「MUST（しなければならない）」、「MUST NOT（してはならない）」、「REQUIRED（必須）」、「SHALL（するべき）」、「SHALL NOT（すべきでない）」、「SHOULD（すべきである）」、「SHOULD NOT（すべきでない）」、「RECOMMENDED（推奨される）」、「MAY（してもよい）」、「OPTIONAL（選択できる）」は、RFC 2119 RFC2119 に記述されているとおりに解釈されます。 2. DSA および ECDSA の表記法
2.1. 鍵パラメータ
DSAとECDSAは、素数サイズの大きな群に対して動作します。この群の演算は容易ですが、離散対数は既存および予測可能な技術では計算不可能です。この群の定義は「鍵パラメータ」と呼ばれます。鍵パラメータは、セキュリティに悪影響を与えることなく、異なる鍵ペア間で共有できます。特にECDSAでは、これが一般的です。
DSAは以下の鍵パラメータを使用します。
p：大きな素数（1024ビット以上）
q：p-1の約数でもある、十分に大きな素数（160ビット以上）
g：pを法とするq位の整数の乗法部分群の生成元
DSAが計算される群は、「g^j mod p」($ g^j \mod p)の値で構成されます。ここで、「^」はべき乗を表し、jは0からq-1（両端を含む）までの範囲です。群のサイズはqです。
ECDSAは以下の主要なパラメータを使用します。
E：与えられた有限体上で定義された楕円曲線
q：曲線位数の約数となる十分に大きな素数（160ビット以上）
G：Eの位数qの点
ECDSAの計算対象となる群は、曲線点jG（点Gと整数jの積）で構成されます。ここで、jは0からq-1までの範囲です。Gは、qG = 0（曲線E上の「無限遠点」）となる点です。群のサイズはqです。これらの表記法はX9.62で説明されている表記法とは若干異なることに注意してください。DSAで使用される表記法と一致させるために、これらの表記法を使用しています。 2.2. 鍵ペア
DSAまたはECDSAの秘密鍵は、整数xをqで割ったものとなります。関連規格では、xは0であってはならないと規定されているため、xは[1, q-1]の範囲の整数となります。
DSAまたはECDSAの公開鍵は、秘密鍵xと鍵パラメータから計算されます。
DSAの場合、公開鍵は整数y = g^x mod pです。
ECDSAの場合、公開鍵は曲線点U = xGです。
2.3. 整数変換
qlenをqのバイナリ長とします。qlenは、qが2^qlenより小さい最小の整数です。これは、符号ビットを除いたqのバイナリ表現のサイズです（qは大きな素数なので奇数となり、2のべき乗に等しい整数の長さに関する曖昧さを回避します）。ビット、オクテット、およびqを法とする整数の文字列に対して機能する5つの変換関数を定義します。qlenはこれらの変換の主なパラメータです。
以下のサブセクションでは、blenとrlenという2つの他の長さを使用します。rlenはqlenに等しく、8の倍数に切り上げられます（qlenが既に8の倍数である場合、rlenはqlenに等しくなります。そうでない場合は、rlenはわずかに大きくなり、最大でqlen+7になります）。rlenは、生成される署名の前半である値rとは無関係であることに注意してください。 blen は入力ビット列の長さ（ビット単位）であり、呼び出しごとに変化する可能性があります。blen は qlen より小さい場合も、等しい場合も、大きい場合もあります。
2.3.1. ビットとオクテット
形式的には、すべての演算はビット列に対して定義されます。列は順序付けられ、最初のビットは左端、最後のビットは右端と呼ばれます。
ほとんどのソフトウェアシステムでは、ビットはオクテット（8ビットの列）にグループ化されます。バイナリデータ（ハッシュ関数の出力など）は、オクテット列として利用できます。適用可能な場合、オクテット内のビットは最上位から最下位の順に順序付けられているとみなします。つまり、オクテット内の最初の（左端）ビットの数値は128、最後の（右端）ビットの数値は1です。
2.3.2. ビット文字列から整数への変換
bits2int変換は、blenビットのシーケンスを入力として受け取り、2^qlen未満の非負整数を出力します。この変換は、以下の手順で構成されます。
1. まず、シーケンスを長さqlenに切り詰めるか拡張します。
qlen < blenの場合、左端のqlenビットが保持され、それ以降のビットは破棄されます。
それ以外の場合、qlen-blenビット（値は0）がシーケンスの左側（つまり、シーケンス順序において入力ビットの前）に追加されます。
2. 結果のシーケンスは、ビッグエンディアン規則に従って整数値に変換されます。入力ビットを b_0（左端）から b_(qlen-1)（右端）とすると、結果の値は次のようになります。
b_02^(qlen-1) + b_12^(qlen-2) + ... + b_(qlen-1)*2^0
bits2int 変換は、次のようにも記述できます。
入力ビットシーケンス（長さ blen）は、ビッグエンディアン規則に従って整数に変換されます。次に、blen が qlen より大きい場合、結果の整数を 2 の blen-qlen 乗で割ります（ユークリッド除算：余りは切り捨てられます）。大きな整数に対する演算の多くのソフトウェア実装では、この除算は blen-qlen ビットの「右シフト」に相当します。
2.3.3.整数からオクテット文字列への変換
q より小さい整数値 x（特に、q を法とする法則で求められた値）は、rlen ビットのシーケンスに変換できます。ここで、rlen = 8*ceil(qlen/8) です。これはビッグエンディアン符号化によって得られるビットシーケンスです。言い換えれば、ビットシーケンス x_i（i は 0 から rlen-1 まで）は、以下の式で表されます。
x = x_02^(rlen-1) + x_12^(rlen-2) + ... + x_(rlen-1)
この変換を int2octets と呼びます。rlen は 8 の倍数（qlen より小さくない最小の 8 の倍数）であるため、結果として得られるビットシーケンスもオクテットシーケンスとなり、この名前が付けられます。
2.3.4. ビット文字列からオクテット文字列へ
bits2octets 変換は、blen ビットのシーケンスを入力として受け取り、rlen ビットのシーケンスを出力します。この変換は、以下の手順で構成されます。
1. 入力シーケンス b は、bits2int 変換によって整数値 z1 に変換されます。
z1 = bit2int(b)
2. z1 を q を法として減算し、z2 (0 から q-1 まで、両端を含む整数) を生成します。
z2 = z1 mod q
z1 は 2^qlen より小さいため、このモジュラー減算は単純な条件付き減算で実装できます。
z2 = z1-q が非負の場合、z1 = z1。それ以外の場合、z2 = z1。
3. z2 は int2octets を適用してオクテットシーケンス (rlen ビットのシーケンス) に変換されます。
2.3.5.使用法
int2octets は、長さ qlen の入力シーケンスであっても、bits2int の逆ではないことに注意してください。int2octets は左側のビットを追加しますが、bits2int は右側のビットを削除します。int2octets は、qlen が 8 の倍数で、ビットシーケンスの長さが既に qlen である場合にのみ、bits2int の逆になります。
bits2int は、標準 DSA および ECDSA における署名生成および検証中に、入力メッセージから計算されたハッシュ値を q を法とする整数に変換するために使用されます。つまり、bits2int によって得られた整数は、q を法としてさらに減算されます。この整数は 2^qlen より小さいため、この減算は最大 1 回の減算で実行できます。
int2octets は、SEC 1 SEC1 のセクション 2.3.7 で「Integer-to-OctetString」という名前で定義されています。これは、ASN.1ベースの構造におけるECDSA秘密鍵(x)のエンコード仕様で使用されます。 bits2octetsは、標準DSAやECDSAでは使用されません。決定論的(EC)DSAの仕様で使用します。
2.4. 署名生成
署名生成では、暗号ハッシュ関数Hと入力メッセージmを用いる。メッセージはまずHによって処理され、長さhlenのビット列である値H(m)が生成される。署名方式全体のセキュリティはhlenとqlenの最小値に依存するため、通常、Hは出力長hlenがqlenとほぼ等しくなるように選択される。しかし、関連規格ではhlenとqlenのあらゆる組み合わせがサポートされている。
次に、以下の手順が適用される。
1. H(m)は、bits2int変換と追加のモジュラー減算を用いて、qを法とする整数に変換される。
h = bits2int(H(m)) mod q
bits2octetsの説明で述べたように、追加のモジュラー減算は条件付き減算に過ぎない。
2. qを法とする乱数（kと表記）が生成される。この値は0であってはならない。したがって、k は 1, q-1 の範囲にあります。このドキュメントの残りの部分では、主に k を生成するプロセスについて説明します。通常の DSA または ECDSA では、k は q-1 個の可能な値の中から一様確率でランダム選択によって選択されます。 3. k と主要なパラメータから、q を法とする値 r が計算されます。
DSA の場合:
r = g^k mod p mod q
(べき乗は p を法として実行され、0 から p-1 の間の数値が生成されます。その後、q を法としてさらに減算されます。)
ECDSA の場合: 点 kG が計算され、その X 座標 (E が定義されている体の元) が整数に変換され、q を法として減算されて r が生成されます。
r が 0 になった場合、新しい k が選択され、r が再度計算されます (これは全く起こり得ないことです)。
4. 値 s (modulo q) は次のように計算されます。
s = (h+x*r)/k mod q
sがゼロになった場合は、新しいkを選択してrとsを再度計算する必要があります（これも同様に起こりそうにありません）。
(r, s) のペアが署名です。署名のエンコード方法は、DSA および ECDSA 標準自体では規定されていません。
一般的な方法は、DER エンコードされた ASN.1 構造 (r と s の順序で並んだ 2 つの整数のシーケンス) を使用することです。
3. 決定論的DSAとECDSA
決定論的(EC)DSAは、入力メッセージmに対して、標準的な(EC)DSA署名生成プロセス（前節で説明）を用いて(EC)DSA署名を生成するプロセスです。ただし、値kはランダムに生成されるのではなく、本節で説明するプロセスによって得られます。
本章では、第2節で説明した表記法を使用します。
3.1. 構成要素
3.1.1. HMAC
HMAC RFC2104は、ハッシュ関数と秘密鍵を用いたメッセージ認証コードの構築法です。ここでは、署名生成または検証の前に入力メッセージの処理に使用されたものと同じハッシュ関数Hを用いたHMACを使用します。 データVに対して鍵Kを用いてHMACを適用するプロセスを、次のように表記します。
HMAC_K(V)
これは、長さhlen（基礎となるハッシュ関数Hの出力長）のビット列を返します。
3.2. k の生成
入力メッセージ m が与えられた場合、以下の処理が適用されます。
a. m をハッシュ関数 H に通して、以下の値を生成します。
h1 = H(m)
（h1 は hlen ビットのシーケンスです。）
b. 以下のように設定します。
V = 0x01 0x01 0x01 ... 0x01
V の長さ（ビット数）が 8*ceil(hlen/8) となるように設定してください。例えば、オクテットベースのシステムで H が SHA-256 の場合、V は値 1 の 32 オクテットのシーケンスに設定されます。このステップおよび以降のすべてのステップでは、ステップ「a」で入力メッセージを処理するために使用したのと同じ H 関数を使用することに注意してください。この選択については、セクション 3.6 で詳しく説明します。
c. 設定:
K = 0x00 0x00 0x00 ... 0x00
K の長さ（ビット数）が 8*ceil(hlen/8) となるように設定してください。
d. 設定:
K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1))
ここで '||' は連結を表します。言い換えれば、鍵 K を用いて、以下の要素を連結したものに対して HMAC を計算します。連結の順序は、V の現在の値、値 0 の 8 ビットのシーケンス、(EC)DSA 秘密鍵 x のエンコード、ハッシュ化されたメッセージ（bits2octets 変換で指定されたとおりに切り詰められたり拡張されたりする場合もあります）。 HMACの結果がKの新しい値です。秘密鍵xは1, q-1の範囲にあるため、int2octetsの適切な入力となり、rlenビットの出力、つまり整数のオクテット数（rlenは8の倍数）が生成されます。 e. 設定：
V = HMAC_K(V)
f. 設定：
K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1))
今回は「内部オクテット」が0x01であることに注意してください。
g. 設定：
V = HMAC_K(V)
h. kの適切な値が見つかるまで、以下のアルゴリズムを適用します。
1. Tを空シーケンスに設定します。Tの長さ（ビット数）をtlenとします。したがって、その時点では tlen = 0 です。
2. tlen < qlen の間、以下の処理を実行します。
V = HMAC_K(V)
T = T || V
3. 計算:
k = bit2int(T)
kの値が1,q-1の範囲内にあり、DSAまたはECDSAに適している場合（つまり、rの値が0ではない場合。セクション3.4を参照）、kの生成は完了です。得られたkの値はDSAまたはECDSAで使用されます。それ以外の場合は、以下の計算を行います。 K = HMAC_K(V || 0x00)
V = HMAC_K(V)
そしてループします（新しいTの生成を試みるなど）。
Tからkを生成する際、bits2intの結果はqと比較されるのであって、qを法として減算されるのではないことに注意してください。値が1からq-1の範囲外の場合、プロセスはループします。単純なモジュラー縮約を実行すると、署名のセキュリティに悪影響を与えるバイアスが生じる可能性があります。
3.3. k 生成の代替説明
前節で説明したプロセスは、実際には SP800-90A および X9.62 の付録 D に記載されている「HMAC_DRBG」擬似乱数生成器から派生したものです。SP800-90A の用語を用いると、k 生成は次のように説明できます。 a. 署名対象メッセージの処理に使用されるハッシュ関数 H と同じハッシュ関数 H でパラメータ化された HMAC を使用して、HMAC_DRBG をインスタンス化します。インスタンス化パラメータは以下のとおりです。
requested_instantiation_security_strength H を基本ハッシュ関数として使用する場合、このパラメータは HMAC_DRBG 実装が受け入れる任意の値に設定します。
prediction_resistance_flag
このパラメータは "false" に設定します。
personalization_string
このパラメータは "Null"（空のビットシーケンス）に設定します。
entropy_input
エントロピー文字列として int2octets(x) を使用します。
nonce
nonce として bits2octets(H(m)) を使用します。
最後の2つのパラメータは、HMAC_DRBGインスタンス化関数自体へのパラメータではなく、インスタンス化中に内部の Get_entropy_input 関数から要求されることに注意してください。決定論的(EC)DSAの場合、実際のエントロピーソースにアクセスすることなく、指定したエントロピー文字列と nonce を使用してHMAC_DRBGを実行する必要があります。
b. HMAC_DRBGから qlen ビットを要求し、得られたビットをbits2int変換によって整数に変換することで、kの候補値を生成します。この手順を、ゼロ以外で q 未満であり、(EC)DSAに適した値が得られるまで繰り返します（セクション3.4を参照）。
署名生成プロセスごとに新しいHMAC_DRBGインスタンスをインスタンス化することに注意してください。ビット生成時に「パーソナライゼーション文字列」や「追加入力」は存在しません。HMAC_DRBGの再シード関数は、外部からも内部HMAC_DRBG処理の結果として呼び出されることもありません。
上記のように、秘密鍵のエンコードを「エントロピー文字列」として、ハッシュ化されたメッセージ（bits2octetsで切り捨てられ拡張された）を「ノンス」として使用します。HMAC_DRBGでは、エントロピー文字列とノンスは単純に結合されて初期シードとなるため、「エントロピー」と「ノンス」の分割は極めて任意です。それぞれにqlenビットを使用することで、ほとんどのHMAC_DRBG実装の入力要件を満たすはずです。
3.4. 使用上の注意
DSAまたはECDSAでは、値kは署名の前半部分（rと呼ばれる）を計算するために使用されます（セクション2.4を参照）。DSAおよびECDSA規格では、rが0の場合、新しいkを選択することが義務付けられています。このような状況では、この文書では値kが「不適切」であり、生成プロセスはループを継続するものとします。
このような状況が発生することは全く考えられません。実際には、rが0となる秘密鍵とメッセージを見つけるには、相当な計算量（ハッシュ関数の原像抵抗性を打ち破るのと同等）が必要になります。したがって、このようなケースが全くの偶然に発生することは考えにくく、攻撃者は巧妙に作成したメッセージでそれを強制することはできません。実際には、このようなコードパスはトリガーされないため、ほとんど最適化を行わずに実装できます。
3.5.根拠
前節で説明したプロセスは、X9.62の付録Dに記載されているkの「承認済み」生成プロセスを、「HMAC_DRBG」擬似乱数生成器を用いて模倣したものです。主な違いは、秘密鍵xとハッシュメッセージH(m)の連結を擬似乱数生成器（PRNG）のシードとして用いることです。「セキュリティレベル」をnビットとする場合、シードエントロピーが少なくともn+64ビットのHMAC_DRBGを使用する必要があります。ただし、鍵xもn+64ビット以上のエントロピーで生成する必要があり、xの長さはqlenであり、これは少なくとも2*nに等しく、n+64よりも大きい必要があります（標準規格で規定されているDSAおよびECDSAでは、qlen >= 160が必要です）。したがって、決定論的ECDSAはX9.62の付録Dのエントロピー要件を満たしていると言えます。 統合を容易にするため、H(m) の代わりにbits2octets(H(m)) を使用します。実際、多くの既存の署名システムはメッセージのハッシュ化をオフロードしており、署名エンジン（秘密鍵にアクセスできる）はH(m) のみを受け取ります。データ帯域幅が制限されているアプリケーションでは、bits2int 変換では後続のビットが無視されるという理由から、H(m) の最初の qlen ビットのみが署名エンジンに転送されます。システムによっては、切り捨てられた H(m) を外部的に q を法として縮約できる可能性があります。これは、(EC)DSA がハッシュ化されたメッセージに対して最初に行う処理だからです。bits2octets の定義により、同じ入力に対して決定論的な (EC)DSA を適用できます。
3.6. バリアント
決定論的(EC)DSAの仕様には、多くの部分が極めて恣意的です。「決定論的(EC)DSA」ではないものの、状況によっては有用となる可能性のあるバリアントを定義することも可能です。
o HMAC入力の一部として、bits2octets(H(m))ではなく、H(m)を直接使用することができます。3.5節で説明したように、bits2octets(H(m))を使用するのは、既に(EC)DSA署名エンジンを使用しているシステムへの統合を容易にするためです。そのためには、既に切り捨てられたハッシュ値を(EC)DSA署名エンジンに送信します。H(m)全体を使用することで、脆弱性が生じることはありません。
o 追加データは、HMACの入力にbits2octets(H(m))の後に連結されて追加される場合があります。
K = HMAC_K(V || 0x00 || int2octets(x) || bit2octets(h1) || k')
ユースケースとしては、高品質な乱数源にアクセスできないシステム上で非決定論的な署名アルゴリズムを必要とするプロトコルが挙げられます。追加データk'が非反復的（例えば、署名カウンタや単調クロック）であることで、「ランダムに見える」署名が暗号学的にプレーンな(EC)DSA署名と区別できないことが保証されます。SP800-90Aの用語では、k'は擬似乱数ビットを生成する際にパラメータとして設定できる「追加入力」です。このバリエーションは、追加データk'の乱数源のランダム性を「強化」するものと考えることができます。 o HMACへの入力としてx（秘密鍵）を使用する代わりに、追加の秘密データを秘密鍵と共に保存し、同じセキュリティ対策を施すことも可能です。この追加データのエントロピーは少なくともnビット、できればn+64ビット以上である必要があります（nは目標セキュリティレベル）。追加の秘密データを使用することで、デランダム化のセキュリティを形式的に証明するのに役立つ可能性がありますが、追加のストレージコストが発生し、既に生成された(EC)DSA秘密鍵との互換性が失われます。
o 同様に、秘密鍵を値zとすることもできます。この値zから、x（通常の(EC)DSAにおける「秘密鍵」）と、kを生成する際にHMACへの入力として使用される別の値x'の両方が、適切な擬似乱数関数（PRF）（HMAC_DRBGなど）によって導出されます。これにより、秘密鍵のストレージ要件を最小限に抑えながら、より容易にセキュリティを証明できますが、秘密鍵の生成に影響を与え、既に生成された鍵ペアとの互換性が失われます。
o この文書では、入力メッセージの処理とHMACのパラメータとして同じハッシュ関数Hを使用します。2つの異なるハッシュ関数を使用することもできますが、その場合、両方のハッシュ関数が十分に安全である必要があります。全体的なセキュリティは、2つのハッシュ関数のうち弱い方、つまり出力が小さい方によって制限されます。HMACに特定の定数ハッシュ関数を使用することは、外部ハッシュ化されたメッセージを受け入れる制約のある実装において、そのハッシュ関数が何であるかに関わらず、HMAC用に1つのハッシュ関数しか実装できないような場合に有用です。
いずれのバリエーションにおいても、主な欠点は、この文書で公開されているテストベクトルに対して検証できなくなることです。
4. セキュリティに関する考慮事項
暗号署名アルゴリズムを適切に実装し使用するには、多くのパラメータを考慮する必要があります。特に、秘密鍵の生成、保管、アクセス制御、および廃棄は機密性の高い操作であり、本文書では一切触れていません。決定論的(EC)DSAは、署名生成時に強力な乱数源、あるいは乱数源そのものを必要としないまま、標準的なDSAまたはECDSA署名方式のセキュリティ特性を実現する方法を示しています。
しかし、秘密鍵生成には、このような強力な乱数源が絶対に必要です。適切な乱数源がないため決定論的(EC)DSAを使用しなければならない状況では、秘密鍵は外部で生成され、署名生成システムにインポートされたか、乱数が利用可能な状況で生成されたものと想定する必要があります。例えば、工場で管理された環境条件下では秘密鍵を生成するスマートカードが、現場で使用され、潜在的な攻撃者の手に渡った後は、ランダムデータの生成が保証されない場合があります。
乱数源要件の廃止と、テストベクトルを用いた実装テストの実施可能性は、DSAおよびECDSA署名実装のセキュリティを強化し、テストが困難な障害条件の回避に役立ちます。決定論的署名方式は、他の状況でも役立ちます。例えば、同じデータ要素が同じ鍵で複数回署名される場合、偽の重複を回避することができます。決定論的署名方式では、毎回同じ署名が生成されるため、重複検出がはるかに容易になります。
逆に、ランダム化の欠如は、一部の高度なプロトコル、例えば一部の投票方式における匿名性に関連するプロトコルにおいて悪影響を及ぼす可能性があります。経験則として、プロトコル全体が他の決定論的署名方式、特にPKCS #1 RFC3447 で規定されているRSA（「タイプ1」パディングを使用し、PSSではない）またはISO 9796-2 ISO-9796-2 が許容するのであれば、決定論的DSAまたはECDSAを、セキュリティ上の問題を追加することなく、純粋なDSAまたはECDSAの代わりに使用することができます。決定論的DSAまたはECDSAが適切なプロトコルとしては、トランスポート層セキュリティ（TLS）RFC5246、セキュアシェル（SSH）プロトコルRFC4251、暗号メッセージ構文（CMS）RFC5652とその派生、X.509公開鍵基盤RFC5280など、多数が挙げられます。 本文書で説明する構成は「デランダム化」として知られています。これは様々な署名方式で提案されています。セキュリティは、k の生成がランダムオラクルの出力と区別できないかどうかに依存します。大まかに言えば、HMAC が PRF（擬似ランダム関数）として動作する限り、HMAC_DRBG はその役割において安全です。HMAC と HMAC_DRBG のセキュリティの詳細については、H2008 および B2006 を参照してください。より正式なデランダム化の扱いについては、LN2009 を参照してください。 本文書で提示されている決定論的 (EC) DSA に残る問題点の一つは、秘密鍵 x の「二重使用」です。これは、署名生成アルゴリズム自体における秘密鍵として、そして k 値を生成するための HMAC_DRBG ベースの擬似ランダムオラクルへの入力として使用されます。
この問題点を解決するには、公開鍵（x から計算される）が既知であっても、HMAC_DRBG がランダムオラクルであり続ける必要があります。 HMACと離散対数の間に共通の構造がないことを考えると、これは妥当な仮定であるように思われます。
サイドチャネル攻撃は、攻撃者が署名処理の実行時間や署名処理の各時点での消費電力など、実装のさまざまな側面を正確に測定できる場合、重要な考慮事項となります。本稿で説明するアルゴリズムの決定論性は、一部のサイドチャネル攻撃において攻撃者にとって有用となる可能性があるため、実装はサイドチャネルを介した秘密鍵の漏洩を防ぐための防御策を講じるべきです。
5. 知的財産の状況
私たちの知る限り、決定論的(EC)DSAは有効な特許で保護されていません。論文BDLSY2011では、BarwoodとWigleyによるデランダム化のアイデアに関する2つの独立した論文（いずれも1997年初頭）と、その数か月後にNaccache、M'Raihi、Levy-dit-Vehelによる特許出願NML1997が示されていますが、この出願は2003年に取り下げられています。この主題に関する他の特許は、私たちの知る限り存在しません。 6. 参考文献
6.1. 規範的な参考文献
FIPS-186-4 米国国立標準技術研究所、「デジタル署名標準（DSS）」、連邦情報処理標準刊行物（FIPS PUB）186-4、2013年7月。 RFC2104 Krawczyk, H.、Bellare, M.、およびR. Canetti、「HMAC：メッセージ認証のための鍵付きハッシュ」、RFC 2104、1997年2月。 RFC2119 Bradner, S.、「RFCで要件レベルを示すキーワード」、BCP 14、RFC 2119、1997年3月。 SEC1 Certicom Research、「SEC 1：楕円曲線暗号（バージョン2.0）」、2009年5月。 SP800-90A 米国国立標準技術研究所、「ランダム署名に関する勧告」 「決定論的乱数ビット生成器を用いた数値生成（改訂版）」、NIST 特別刊行物 800-90A、2012年1月。
X9.62 米国規格協会、「金融サービス業界向け公開鍵暗号：楕円曲線デジタル署名アルゴリズム（ECDSA）」、ANSI X9.62-2005、2005年11月。 6.2.参考文献
B2006 Bellare, M., 「NMACとHMACの新しい証明：衝突耐性のないセキュリティ」、Crypto 2006、LNCS 4117、2006年8月。 BDLSY2011 Bernstein, D., Duif, N., Lange, T., Schwabe, P., and B. Yang, 「高速高セキュリティ署名」、Cryptology ePrint Archive Report 2011/368、2011年9月。 FIPS-180-4 米国国立標準技術研究所（NIST）、「セキュアハッシュ標準（SHS）」、連邦情報処理標準出版物（FIPS PUB）180-4、2012年3月。 H2008 Hirose, S., 「NIST SP 800-90におけるHMACを用いたDRBGのセキュリティ分析」、情報セキュリティアプリケーション (WISA 2008)、LNCS 5379、2008年9月。 ISO-9796-2 国際標準化機構、「情報技術 - セキュリティ技術 - メッセージ復元を可能にするデジタル署名方式 - パート2：整数因数分解に基づくメカニズム」、ISO/IEC 9796-2:2010、2010年12月。 NML1997 Naccache, D.、M'Raihi, D.、およびF. Levy-dit-Vehel、「ランダム描画を必要とする暗号化システムのためのハッシュ符号化関数に基づく擬似乱数生成器」、WIPO特許公開 WO/1998/051038、1998年5月。 RFC3447 Jonsson, J. および B. Kaliski、「公開鍵暗号標準 (PKCS) #1: RSA 暗号仕様 バージョン 2.1」、RFC 3447、2003年2月。 RFC4251 Ylonen, T. および C. Lonvick、「セキュアシェル (SSH) プロトコルアーキテクチャ」、RFC 4251、2006年1月。 RFC5246 Dierks, T. および E. Rescorla, "トランスポート層セキュリティ (TLS) プロトコル バージョン 1.2", RFC 5246, 2008年8月.
RFC5280 Cooper, D., Santesson, S., Farrell, S., Boeyen, S., Housley, R., および W. Polk, "インターネット X.509 公開鍵インフラストラクチャ証明書および証明書失効リスト (CRL) プロファイル", RFC 5280, 2008年5月. RFC5652 Housley, R., "暗号メッセージ構文 (CMS)", STD 70, RFC 5652, 2009年9月. 付録A. 例
A.1. 詳細な例
ここでは、サンプルメッセージと鍵を用いてkを生成する際に得られる中間値を詳細に説明します。バイナリ曲線を使用するのは、この曲線が標準であり、群順序長（qlen）が8の倍数ではないためです。これは、整数とビット列間の変換がどのように行われるかを詳細に示しています。
A.1.1. 鍵ペア
FIPS-186-4で記述されている曲線K-163（X9.62では「ansix9t163k1」とも呼ばれます）上のECDSAを検討します。この曲線は、体GF(2^163)上で定義されます。体要素は163ビットの文字列に符号化されます。 慣用的な基点の位数は素数値です。
q = 0x40000000000000000000020108A2E0CC0D99F8A5EF
長さは qlen = 163 ビットです。
秘密鍵は、次のとおりです。
x = 0x09A4D6792295A7F730FC3F2B49CBC0F62E862272F
対応する公開鍵は曲線点 U = xG です。この点は、体 GF(2^163) の元である 2 つの座標を持ちます。
これらの要素は、X9.62 のセクション A.5.6 に記載されている手順を用いて整数に変換することができ、2つの公開点座標が得られます。 Ux = 0x79AEE090DB05EC252D5CB4452F356BE198A4FF96F
Uy = 0x782E29634DDC9A31EF40386E896BAA18B53AFA5A3
A.1.2. k の生成
この例では、ハッシュ関数 SHA-256 FIPS-180-4 を使用します。入力メッセージは、文字列 "sample" の UTF-8 エンコード（6オクテット、つまり48ビット）です。 ハッシュ化された入力メッセージ h1 = SHA-256(m) は次のとおりです。
h1
AF 2B DB E1 AA 9B 6E C1 E2 AD E1 D6 94 F4 1F C7
1A 83 1D 02 68 E9 89 15 62 11 3D 8A 62 AD D1 BF
（32オクテット。各オクテットの値は16進数で表記）。
秘密鍵 x を int2octets 変換を用いてオクテット列に変換します。
int2octets(x)
00 9A 4D 67 92 29 5A 7F 73 0F C3 F2 B4 9C BC 0F
62 E8 62 27 2F
注: x の具体的な値は数値的には160ビット、つまり20オクテットに収まりますが、エンコード長は q の長さ（163ビット）によって決まるため、x は21オクテットにエンコードされます。
また、bits2octetsを用いてハッシュ化されたメッセージを切り詰めたり拡張したりします。
bits2octets(h1)
01 79 5E DF 0D 54 DB 76 0F 15 6D 0D AC 04 C0 32
2B 3A 20 42 24
手順b～g（セクション3.2参照）では、K変数とV変数の値を計算します。これらの変数は256ビット（ハッシュ関数の出力長を8の倍数に切り上げた値）のシーケンスです。ここで、連続する値を再現します。
ステップb後のV：
01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
01 01 01 01 01 01 01 01 01 01 01 01 01 01
ステップc後のK：
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00
ステップd後のK：
09 99 9A 9B FE F9 72 D3 34 69 11 88 3F AD 79 51
D2 3F 2C 8B 47 F4 20 22 2D 11 71 EE EE AC 5A B8
ステップe後のV：
D5 F4 03 0F 75 5E E8 6A A1 0B BA 8C 09 DF 11 4F
F6 B6 11 1C 23 85 00 D1 3C 73 43 A8 C0 1B EC F7
ステップf後のK：
0C F2 FE 96 D5 61 9C 9E F5 3C B7 41 7D 49 D3 7E
A6 8A 4F FE D0 D7 E6 23 E3 86 89 28 99 11 BD 57
ステップ g の後の V:
78 34 57 C1 CF 31 48 A8 F2 A9 AE 73 ED 47 2F A9
8E D9 CD 92 5D 8E 96 4C E0 76 4D EF 3F 84 2B 9A
ステップ h では、最後のループを実行します。SHA-256 を用いた HMAC を使用すると 256 ビットの出力が生成され、T に必要なのは 163 ビットだけなので、1 回の HMAC 呼び出しで次の T が生成されます。
T (1 回目の試行)
93 05 A4 6D E7 FF 8E B1 07 19 4D EB D3 FD 48 AA
20 D5 E7 65 6C BE 0E A6 9D 2A 8D 4E 7C 67 31 4A
これを bits2int で整数に変換すると、k の最初の候補が生成されます。
k1 = 0x4982D236F3FFC758838CA6F5E9FEA455106AF3B2B
この値は q-1 より大きいため、ループを実行する必要があります。まず、KとVの新しい値を計算しなければなりません。
新しいK
75 CB 5C 05 B2 A7 8C 3D 81 DF 12 D7 4D 7B E0 A0
E9 4A B1 98 15 78 1D 4D 8E 29 02 A7 9D 0A 66 99
新しいV
DC B9 CA 12 61 07 A9 C2 7C E7 7B A5 8E A8 71 C8
C9 12 D8 35 EA DD C3 05 F2 44 5D 88 F6 6C 4C 43
次に新しいTを計算します。
T (2回目の試行)
C7 0C 78 60 8A 3B 5B E9 28 9B E9 0E F6 E8 1A 9E
2C 15 16 D5 75 1D 2F 75 F5 00 33 E4 5F 73 BD EB
そしてkの新しい候補：
k2 = 0x63863C30451DADF4944DF4877B740D4F160A8B6AB
k2もq-1より大きいので、再度ループします：
新しいK (2)
0A 5A 64 B9 9C 05 95 20 10 36 86 CB 6F 36 BC FC
A7 88 EB 3B CF 69 BA 66 A5 BB 08 0B 05 93 BA 53
新しいV (2)
0B 3B 19 68 11 B1 9F 6C 6F 72 9C 43 F3 5B CF 0D
FD 72 5F 17 CA 34 30 E8 72 14 53 E5 55 50 A1 8F
T (3回目)
47 5E 80 E9 92 14 05 67 FC C3 A5 0D AB 90 FE 84
BC D7 BB 03 63 8E 9C 46 56 A0 6F 37 F6 50 8A 7C
そして、最終的にkの許容値が得られます。
k = 0x23AF4074C90A02B3FE61D286D5C87F425E6BDD81B
A.1.3. 署名
秘密鍵と先ほど生成したkの値を使って、標準的なECDSAメカニズムを用いて署名を計算できます。
まず、点kGを計算し、その点のX座標を整数に変換し、qを法として減算することで、署名の前半部分を生成します。
r = 0x113A63990598A3828C407C0F4D2438D990DF99A7F
これを、秘密鍵x、上記で計算したk、およびh = bits2int(h1)と組み合わせて、署名の後半部分を計算します。
s = 0x1313A2E03F5412DDB296A22E2C455335545672D9F
ECDSA署名は整数のペアです。署名をビット（またはオクテット）のシーケンスで表すことを要求する多くのプロトコルでは、DER規則に従って、2つの整数値のASN.1シーケンスとして署名をエンコードするのが一般的です。結果として、48オクテットの署名は次のようになります。
30 2E 02 15 01 13 A6 39 90 59 8A 38 28 C4 07 C0
F4 D2 43 8D 99 0D F9 9A 7F 02 15 01 31 3A 2E 03
F5 41 2D DB 29 6A 22 E2 C4 55 33 55 45 67 2D 9F
A.2. テストベクトル
以下のセクションでは、DSAとECDSAの両方について、様々な鍵サイズとハッシュ関数のテストベクトルを示します。
すべての数値は16進数表記で示します。各署名は、rとsという2つの整数で構成されます。多くの実装では、これらの整数を単一のASN.1構造またはその他の符号化規則にエンコードしますが、これはこのドキュメントの範囲外です。また、内部で使用されるkの値も示します。
各鍵について、2つの異なる入力メッセージに対応する10個の署名と、5つのSHA FIPS-180-4関数（SHA-1、SHA-224、SHA-256、SHA-384、SHA-512）を示します。2つの入力メッセージは、文字列「sample」と「test」（引用符なし）のUTF-8エンコードであり、それぞれ長さは48ビットと32ビットです。 (コード省略)
A.3. サンプルコード
ここでは、決定論的DSAのサンプル実装を示します。これは説明目的であり、例えば、このコードは秘密鍵のサイドチャネル漏洩を回避するための処理は一切行っていません。このコードはJavaプログラミング言語で記述されています。「ランダム」値kの実際の生成はcomputek()メソッドで行われます。ハッシュ関数とHMACの実装はJava仮想マシン（JVM）が提供するものと想定しています。
(コード省略)